package cn.moefly.algorithm.sort;

import java.util.Arrays;
import java.util.function.BiFunction;

public class BubbleSort implements SortAlgoRithm {

    /**
     * 冒泡排序
     * 时间复杂度：（On^2）
     * 空间复杂度：（O1）
     * 稳定性： 稳定
     *
     * 注意点：
     * 1. 注意冒泡的方向，必须要把泡泡冒到外层循环变动的地方（如当前的代码是在末尾开始减少，所以要冒到末尾），简单地记忆就是内外循环要反着来
     * 2. 注意边界，+1 -1 操作都可能会超界，如当前实现中，内层循环由于有+1操作，所以j不可以直接到13，必须要取条件i-1
     * 3. 使用位运算操作就可以不使用辅助快速地交换两个数，具体原理是：
     *      通过异或运算保存差异部分，然后再用差异部分与其中一个数运算就可以得到另一个数 (A^B)^A = (A^A)^B = B
     *      1）1100 ^ 1011 = 0111
     *      2）0111 ^ 1100 = 1011
     *      2) 0111 ^ 1011 = 1100
     *
     */
    @Override
    public int[] sort(int[] source,int type) {
        BiFunction<Integer,Integer,Boolean> compare = type == ASC ? GT : LT ;
        var arr = source.clone();
        for (int i = arr.length; i > 0; --i) {
            for(int j = 0 ; j < i-1; ++j){
                if (compare.apply(arr[j] , arr[j+1])){
                    arr[j] = arr[j] ^ arr[j+1];
                    arr[j+1] = arr[j] ^ arr[j+1];
                    arr[j] = arr[j] ^ arr[j+1];
                }
            }
        }
        return arr;
    }

}
